//
// Created by martin on 5/12/22.
//

//-----------------------------------------------
// https://leetcode.cn/problems/number-of-provinces/
// 省份数量
// 并查集问题

#include <bits/stdc++.h>

using namespace std;

class Solution {
public:
    // 并查集 求连通分量
    int findCircleNum(vector<vector<int>>& isConnected) {
        if (isConnected.empty() || isConnected[0].empty()) return 0;

        int ans = 0;
        vector<int> fa;
        fa.resize(isConnected.size() + 1);
        // init
        for (int i = 1; i < fa.size(); ++i) {
            fa[i] = i;
        }

        // 输入边, 合并集合
        for (int i = 0; i < isConnected.size(); ++i) {
            for (int j = i + 1; j < isConnected[i].size(); ++j) {
                int x, y;
                if (isConnected[i][j]) {
                    x = i + 1; y = j + 1;
                    Union(fa, x, y);
                }
            }
        }

        for (int i = 1; i < fa.size(); ++i) {
            if (fa[i] == i) {
                ans++;
            }
        }
        return ans;
    }

    void Union(vector<int>& fa, int x, int y) {
        int a = Find(fa, x);
        int b = Find(fa, y);
        if (a != b) {
            fa[a] = b;
        }
    }

    int Find(vector<int>& fa, int x) {
        if (x != fa[x]) {
            fa[x] = Find(fa, fa[x]);
        }
        return fa[x];
    }
};

int main()
{
    Solution s;

    { // test case 1
        vector<vector<int>> vec1 = {
                {1, 1, 0},
                {1, 1, 0},
                {0, 0, 1}
        };
        int res = s.findCircleNum(vec1);
        assert(res == 2);
    }

    { // test case 2
        vector<vector<int>> vec2 = {
                {1,0,0},
                {0,1,0},
                {0,0,1}
        };
        int res = s.findCircleNum(vec2);
        assert(res == 3);
    }
    return 0;
}
